Матч 303, Спиральные числа (SpiralNumbers)

Дивизион 2, Уровень 2; Дивизион 1, Уровень 1

Расположим все натуральные числа следующим образом:

21 22 23 24 25 26

20 7 8 9 10 ...

19 6 1 2 11 ...

18 5 4 3 12 ...

17 16 15 14 13 ...

В задаче необходимо найти номер строки и колонки, в которых находится заданное число n. Число 1 записано в центре и имеет координаты (0, 0). Строки нумеруются сверху вниз, столбцы – слева направо. Например, число 3 имеет координаты (1, 1).

Класс: SpiralNumbers

Метод: string getPosition(int n)

Ограничения: 1 £ n £ 2,147,483,647.

Вход. Натуральное число n.

Выход. Координаты числа n в виде строки “(R, C)”, где R – номер строки, а C – номер столбца.

Пример входа

n

2

7

24

765409

Пример выхода

“(0,1)”

“(-1,-1)”

“(-2,1)”

“(-437,221)”

РЕШЕНИЕ

моделирование + сетки

Задачу решим обычным моделированием движения по спирали, заметив, что от центра (точки с координатами (0, 0)) числа движутся по правилу: 1 шаг вправо, 1 шаг вниз, 2 шага влево, 2 шага вверх, 3 шага вправо и так далее.

ПРОГРАММА

#include <cstdio>

#include <string>

using namespace std;

int x[] = {0, 1, 0, -1};

int y[] = {1, 0, -1, 0};

int xpos, ypos;

class SpiralNumbers

{

public:

string getPosition(int n)

{

char res[20];

int step = 1, dir = 0, cur = 1;

int xpos = 0, ypos = 0, c;

while(1)

{

for(c = 0; c <= 1; c++)

{

if (n - cur > step)

{

xpos += step * x[dir]; ypos += step * y[dir];

dir = (dir + 1) % 4;

cur += step;

} else

{

xpos += (n - cur) * x[dir]; ypos += (n - cur) * y[dir];

sprintf(res,"(%d,%d)",xpos,ypos);

return (string)res;

}

}

step++;

}

}

};